package 剑指II;

import 链表.ListNode;

import java.util.Stack;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-10
 **/

public class Jz027回文链表 {

    /**
     * 给定一个链表的 头节点 head ，请判断其是否为回文链表。
     * 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
     * <p>
     * 示例 1：
     * 输入: head = [1,2,3,3,2,1]
     * 输出: true
     * 示例 2：
     * 输入: head = [1,2]
     * 输出: false
     *  
     * 提示：
     * 链表 L 的长度范围为 [1, 105]
     * 0 <= node.val <= 9
     *  
     * 进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     */

    public boolean isPalindrome(ListNode head) {

        Stack<ListNode> stack = new Stack<>();

        ListNode cur = head;
        while (cur != null) {
            stack.add(cur);
            cur = cur.next;
        }

        ListNode last = null;

        while (stack.peek() != head && stack.peek() != last) {
            cur = stack.pop();
            if (cur.val != head.val) {
                return false;
            }
            last = head;
            head = head.next;
        }

        return true;
    }

    public static void main(String[] args) {
        Jz027回文链表 n = new Jz027回文链表();
        ListNode listNode = ListNode.createListNode(new int[]{1, 2, 2, 1});
        boolean result = n.isPalindrome(listNode);
        System.out.println(result);
    }

}
